//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
//
// Related Topics 链表 双指针 👍 2163 👎 0


/**
 * [0019]删除链表的倒数第 N 个结点(remove-nth-node-from-end-of-list)
 * <p>
 * 算法: 双指针
 * <br>
 * 时间复杂度: O(n)
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点:
 * <br>
 * 1. 链表节点的引用, 要删除当前节点, 必须找到上一个节点
 * 2. 在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。
 * 这样一来，我们就不需要对头节点进行特殊的判断了。
 *
 * @author yonxao
 * @since 2022-08-11 12:38:24
 */
class RemoveNthNodeFromEndOfList {
    @SuppressWarnings("all")
            //leetcode submit region begin(Prohibit modification and deletion)
            /**
             * Definition for singly-linked list.
             * public class ListNode {
             *     int val;
             *     ListNode next;
             *     ListNode() {}
             *     ListNode(int val) { this.val = val; }
             *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
             * }
             */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            ListNode fast = head;
            ListNode slow = dummy;

            for (int i = 0; i < n; i++) {
                fast = fast.next;
            }

            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }

            slow.next = slow.next.next;
            return dummy.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" + "val=" + val + ", next=" + next + '}';
        }
    }

    @SuppressWarnings("all")
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = 2;
        // int[] arr = {1};
        // int n = 1;

        ListNode head = new ListNode(arr[0]);
        ListNode curr = head;
        for (int i = 1; i < arr.length; i++) {
            curr.next = new ListNode(arr[i]);
            curr = curr.next;
        }

        ListNode first = removeNthFromEnd(head, n);
        System.out.println(first);
    }

    /**
     * 算法: 双指针
     * <br>
     * 时间复杂度: O(n)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 知识点:
     * <br>
     * 1. 链表节点的引用
     */
    public static ListNode first(ListNode head, int n) {
        // 双指针；要删除的指针（慢指针），从头开始；快指针，从第 n 个开始，当快指针达到末尾时，删除慢指针节点
        ListNode temp = head;
        ListNode fast = head;
        ListNode slow = head;

        int i = 0;
        while (i < n && fast != null) {
            fast = fast.next;
            i++;
        }

        if (i != n) {
            throw new IllegalArgumentException("链表长度小于 n");
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (slow.next == null) {
            slow = null; // 让上一个节点的 next 为 null 才好使
        } else {
            slow.next = slow.next.next;
        }

        return temp;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 双指针；要删除的指针（慢指针），从头开始；快指针，从第 n 个开始，当快指针达到末尾时，删除慢指针节点
        ListNode dummy = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // while (fast.next != null) {
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
}